{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Unique Good Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfUniqueGoodSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同的好子序列数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串&nbsp;<code>binary</code>&nbsp;。&nbsp;<code>binary</code>&nbsp;的一个 <strong>子序列</strong>&nbsp;如果是 <strong>非空</strong>&nbsp;的且没有 <b>前导</b>&nbsp;<strong>0</strong>&nbsp;（除非数字是 <code>\"0\"</code>&nbsp;本身），那么它就是一个 <strong>好</strong>&nbsp;的子序列。</p>\n",
    "\n",
    "<p>请你找到&nbsp;<code>binary</code>&nbsp;<strong>不同好子序列</strong>&nbsp;的数目。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果&nbsp;<code>binary = \"001\"</code>&nbsp;，那么所有 <strong>好</strong>&nbsp;子序列为&nbsp;<code>[\"0\", \"0\", \"1\"]</code>&nbsp;，所以 <b>不同</b>&nbsp;的好子序列为&nbsp;<code>\"0\"</code> 和&nbsp;<code>\"1\"</code>&nbsp;。 注意，子序列&nbsp;<code>\"00\"</code>&nbsp;，<code>\"01\"</code>&nbsp;和&nbsp;<code>\"001\"</code>&nbsp;不是好的，因为它们有前导 0 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回&nbsp;<code>binary</code>&nbsp;中&nbsp;<strong>不同好子序列</strong>&nbsp;的数目。由于答案可能很大，请将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong> 后返回。</p>\n",
    "\n",
    "<p>一个 <strong>子序列</strong>&nbsp;指的是从原数组中删除若干个（可以一个也不删除）元素后，不改变剩余元素顺序得到的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>binary = \"001\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>好的二进制子序列为 [\"0\", \"0\", \"1\"] 。\n",
    "不同的好子序列为 \"0\" 和 \"1\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>binary = \"11\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>好的二进制子序列为 [\"1\", \"1\", \"11\"] 。\n",
    "不同的好子序列为 \"1\" 和 \"11\" 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>binary = \"101\"\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>好的二进制子序列为 [\"1\", \"0\", \"1\", \"10\", \"11\", \"101\"] 。\n",
    "不同的好子序列为 \"0\" ，\"1\" ，\"10\" ，\"11\" 和 \"101\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= binary.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>binary</code>&nbsp;只含有&nbsp;<code>'0'</code>&nbsp;和&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-unique-good-subsequences](https://leetcode.cn/problems/number-of-unique-good-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-unique-good-subsequences](https://leetcode.cn/problems/number-of-unique-good-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"001\"', '\"11\"', '\"101\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        f,g,mod,opt=[0,0],[0,0],1000000007,0\n",
    "        for i in range(len(binary)-1,-1,-1):\n",
    "            if(binary[i]=='0'):f[0],g[0]=(f[1]+2*f[0]-g[0]+1+mod)%mod,(f[1]+f[0]+1)%mod;opt=1\n",
    "            else:f[1],g[1]=(2*f[1]+f[0]+1-g[1]+mod)%mod,(f[1]+f[0]+1)%mod\n",
    "        return (f[1]+opt)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == \"0\":\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        \n",
    "        ans = (even + odd + (\"0\" in binary)) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == \"0\":\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        return (even + odd + (\"0\" in binary)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod= 10**9 + 7\n",
    "        pre = [0, 0]  # 0结尾， 1结尾\n",
    "        zero = 0\n",
    "        for w in binary:\n",
    "            cur = [0, 0]\n",
    "            if w == \"0\":\n",
    "                cur[0] = pre[0]+pre[1]\n",
    "                cur[1] = pre[1]\n",
    "                zero = 1\n",
    "            else:\n",
    "                cur[1] = pre[0] + pre[1] + 1\n",
    "                cur[0] = pre[0]\n",
    "            pre =[x%mod for x in cur]\n",
    "        return (sum(pre) + zero) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == \"0\":\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        \n",
    "        ans = (even + odd + (\"0\" in binary)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == \"0\":\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        \n",
    "        ans = (even + odd + (\"0\" in binary)) % mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        mod = 10 ** 9 + 7\n",
    "        even, odd = 0, 0\n",
    "        for ch in binary:\n",
    "            if ch == '0':\n",
    "                even = (even + odd) % mod \n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        return (even + odd + int('0' in binary)) % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        a, b = 0, 0\n",
    "        for ch in binary:\n",
    "            if ch == '0':\n",
    "                a += b\n",
    "                a %= kmod\n",
    "            else:\n",
    "                b += a + 1\n",
    "                b %= kmod\n",
    "        \n",
    "        ans = (a + b + ('0' in binary)) % kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp0,dp1 = 0,0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if binary[i] == '0':\n",
    "                dp0 = (dp0 + dp1 + 1) % mod\n",
    "            else:\n",
    "                dp1 = (dp0 + dp1 + 1) % mod\n",
    "            \n",
    "        return (dp1 + int('0' in binary)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10 ** 9 +7\n",
    "        a = b = 0\n",
    "        for c in binary:\n",
    "            if c == '0':\n",
    "                a = (a + b) % mod\n",
    "            else:\n",
    "                b = (a + b + 1) % mod\n",
    "        return (a + b + ('0' in binary)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        MOD = 10 ** 9 + 7 \n",
    "        flag = even = odd = 0\n",
    "        for i in binary:\n",
    "            if i == \"1\":\n",
    "                odd = (even + odd + 1) % MOD\n",
    "            else:\n",
    "                flag = 1\n",
    "                even = (even + odd) % MOD\n",
    "        return (even + odd + flag) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        f = g = 0\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        for c in binary:\n",
    "            if c == '0':\n",
    "                g = (g + f) % mod\n",
    "                ans = 1\n",
    "            else:\n",
    "                f = (f + g + 1) % mod\n",
    "        ans = (ans + f + g) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        p = int(1e9 + 7)\n",
    "        ret = 0\n",
    "        if '1' not in binary:\n",
    "            return 1\n",
    "        if '0' in binary:\n",
    "            ret = 1\n",
    "        for i in range(0, len(binary)):\n",
    "            if binary[i] == '1':\n",
    "                break\n",
    "        binary = binary[i+1:]\n",
    "        f1 = f0 = 0\n",
    "        tot = 1\n",
    "        for i in range(0, len(binary)):\n",
    "            if binary[i] == '1':\n",
    "                tot, f1 = (tot + tot - f1) % p, tot\n",
    "            elif binary[i] == '0':\n",
    "                tot, f0 = (tot + tot - f0) % p, tot\n",
    "        ret += tot % p\n",
    "        return ret % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        MOD = 10**9+7\n",
    "        f0 = f1 = 0\n",
    "        falg = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if binary[i] == '0':\n",
    "                falg = 1\n",
    "                f0 = f0 + f1 +1\n",
    "            else:\n",
    "                f1 = f0 + f1 +1\n",
    "        ans = (f1 + falg) %MOD\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == '0':\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        \n",
    "        ans = (even + odd + (\"0\" in binary)) % mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        even = odd = 0\n",
    "        for ch in binary:\n",
    "            if ch == \"0\":\n",
    "                even = (even + odd) % mod\n",
    "            else:\n",
    "                odd = (even + odd + 1) % mod\n",
    "        \n",
    "        ans = (even + odd + (\"0\" in binary)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        mod = 10 ** 9 + 7\n",
    "        zero = 0\n",
    "        dp0,dp1 = 0,0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if binary[i] == '0':\n",
    "                zero = 1\n",
    "                dp0 = (dp0 + dp1 + 1) % mod\n",
    "            else: \n",
    "                dp1 = (dp0 + dp1 + 1) % mod\n",
    "            \n",
    "        return (dp1 + zero) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        mod = 10 ** 9 + 7\n",
    "        zero = 0\n",
    "        dp0,dp1 = 0,0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if binary[i] == '0':\n",
    "                zero = 1\n",
    "                dp0 = (dp0 + dp1 + 1) % mod\n",
    "            else: \n",
    "                dp1 = (dp0 + dp1 + 1) % mod\n",
    "            \n",
    "        return (dp1 + zero) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "\n",
    "        even, odd = 0, 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for ch in binary:\n",
    "            if ch == '0':\n",
    "                even = odd + even\n",
    "            else:\n",
    "                odd = odd + even + 1\n",
    "        \n",
    "        return (odd + even + int('0' in binary)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n, MOD = len(binary), 1000000007\n",
    "        for srt,v in enumerate(binary):\n",
    "            if v=='1': break\n",
    "        else: return 1\n",
    "        if '0' not in binary: return n\n",
    "        has, p0, p1 = [0]*(n+2), n, n+1\n",
    "        for i in range(n-1,srt-1,-1):\n",
    "            has[i] = (1 + has[p0] + has[p1]) % MOD\n",
    "            if binary[i]=='1': p1 = i\n",
    "            else: p0 = i\n",
    "        return has[i] + 1\n",
    "\n",
    "# 作者：ding-fei-5\n",
    "# 链接：https://leetcode.cn/problems/number-of-unique-good-subsequences/solution/dong-tai-gui-hua-11xing-ji-jian-1005857-n77ww/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        if '1' not in binary:\n",
    "            return 1\n",
    "        p = int(1e9 + 7)\n",
    "        binary = binary[::-1]\n",
    "        dp = [[0] * 2 for _ in range(len(binary))]\n",
    "        dp[0][int(binary[0])] = 1\n",
    "        for i in range(1, len(binary)):\n",
    "            dp[i][1^int(binary[i])] = dp[i-1][1^int(binary[i])]\n",
    "            dp[i][int(binary[i])] += (dp[i-1][0] + dp[i-1][1] + 1) % p\n",
    "        return (dp[len(binary)-1][1] + ('0' in binary)) % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        n = len(binary)\n",
    "        dp = [[0, 0] for _ in range(n + 1)]\n",
    "\n",
    "        for i, ch in enumerate(binary, 1):\n",
    "            dp[i] = dp[i - 1][::]\n",
    "            dp[i][int(ch)] = (sum(dp[i - 1]) + (ch == '1')) % kmod\n",
    "        \n",
    "        return (sum(dp[-1]) + ('0' in binary)) % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:\n",
    "        if(len(binary) == 1):\n",
    "            return 1\n",
    "        MOD = 10**9 + 7\n",
    "        dp = [[0, 0] for _ in range(len(binary))]\n",
    "        reversed_binary = ''.join(reversed(binary))\n",
    "        if reversed_binary[0] == '0':\n",
    "            dp[0][0] = 1\n",
    "        else:\n",
    "            dp[0][1] = 1\n",
    "        for i in range(1, len(binary)):\n",
    "            if reversed_binary[i] == '0':\n",
    "                dp[i][0] = (dp[i-1][0] + dp[i-1][1] + 1) % MOD\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = (dp[i-1][0] + dp[i-1][1] + 1) % MOD\n",
    "        ans = (dp[len(binary)-1][1]) % MOD  \n",
    "        print(ans)  \n",
    "        if \"0\" in binary:\n",
    "            ans = (ans + 1) % MOD\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfUniqueGoodSubsequences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * 2 for _ in range(n + 1)]\n",
    "        for i in reversed(range(n)):\n",
    "            if s[i] == \"0\":\n",
    "                dp[i][1] = dp[i + 1][1]\n",
    "                dp[i][0] = dp[i + 1][1] + dp[i + 1][0] + 1\n",
    "                dp[i][0] %= mod\n",
    "            else:\n",
    "                dp[i][0] = dp[i + 1][0]\n",
    "                dp[i][1] = dp[i + 1][1] + dp[i + 1][0] + 1\n",
    "                dp[1][1] %= mod\n",
    "        return (dp[0][1] + (\"0\" in s)) % mod\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
